VonNeumann Margolus 邻域 可逆CA
邻域定义了元胞之间的交互范围，是CA最重要的设计决策之一。本课深入比较不同邻域，特别关注Von Neumann邻域和Margolus邻域——后者是物理仿真的关键工具。
常见邻域类型：
邻域决定了信息传播的"形状"和速度：
信息传播的"光锥"：
Moore：经过t步后，影响范围是以起点为中心的正方形，边长2t+1
Von Neumann：经过t步后，影响范围是菱形（旋转45°的正方形）
Hexagonal：经过t步后，影响范围接近圆形
这意味着：对于物理仿真，六角形网格最接近真实世界的各向同性！
// ============================================================================
// life_vonneumann.v - Von Neumann邻域生命游戏引擎
// 只考虑上下左右4个正交邻居
// 默认规则: B2/S234（适应4邻居的计数范围0-4）
// ============================================================================
module life_vonneumann #(
parameter WIDTH = 64,
parameter HEIGHT = 64,
parameter BORN = 5'b00100, // B2: 位2=1表示2个邻居出生
parameter SURVIVE = 5'b01110 // S123: 位1,2,3=1
)(
input wire clk,
input wire rst_n,
input wire enable,
input wire init,
input wire [WIDTH*HEIGHT-1:0] seed,
output wire [WIDTH*HEIGHT-1:0] state,
output wire [31:0] generation,
output wire [31:0] population
);
reg [WIDTH*HEIGHT-1:0] curr;
wire [WIDTH*HEIGHT-1:0] nxt;
genvar gx, gy;
generate
for (gy = 0; gy < HEIGHT; gy = gy + 1) begin : gen_row
for (gx = 0; gx < WIDTH; gx = gx + 1) begin : gen_col
localparam integer idx = gy * WIDTH + gx;
localparam integer xm = (gx == 0) ? WIDTH-1 : gx-1;
localparam integer xp = (gx == WIDTH-1) ? 0 : gx+1;
localparam integer ym = (gy == 0) ? HEIGHT-1 : gy-1;
localparam integer yp = (gy == HEIGHT-1) ? 0 : gy+1;
// Von Neumann邻域：仅4个正交邻居
wire [2:0] ncount = curr[ym*WIDTH+gx] + // 上
curr[gy*WIDTH+xm] + // 左
curr[gy*WIDTH+xp] + // 右
curr[yp*WIDTH+gx]; // 下
wire self = curr[idx];
assign nxt[idx] = self ? SURVIVE[ncount] : BORN[ncount];
end
end
endgenerate
reg [31:0] gen_reg;
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
curr <= {WIDTH*HEIGHT{1'b0}};
gen_reg <= 32'd0;
end else if (init) begin
curr <= seed;
gen_reg <= 32'd0;
end else if (enable) begin
curr <= nxt;
gen_reg <= gen_reg + 32'd1;
end
end
assign state = curr;
assign generation = gen_reg;
integer p;
reg [31:0] pop_reg;
always @(*) begin
pop_reg = 32'd0;
for (p = 0; p < WIDTH*HEIGHT; p = p + 1)
pop_reg = pop_reg + curr[p];
end
assign population = pop_reg;
endmoduleMargolus邻域由Norman Margolus在1984年提出，是构造可逆CA的关键技术。
Margolus邻域原理：
将网格分为2×2的块。奇数步（t为奇数）更新"左上对齐"的块，偶数步更新"偏移半格"的块。
关键性质：
块变换规则：2×2块有2⁴=16种可能状态，因此规则是16位查找表
// ============================================================================
// ca_margolus.v - Margolus邻域CA引擎
// 2×2块交替更新，支持可逆规则
// 关键：规则必须是双射（可逆），否则会丢失信息
// ============================================================================
module ca_margolus #(
parameter WIDTH = 64,
parameter HEIGHT = 64,
parameter [15:0] BLOCK_RULE = 16'h6996 // XOR奇偶规则（可逆）
)(
input wire clk,
input wire rst_n,
input wire enable,
input wire init,
input wire [WIDTH*HEIGHT-1:0] seed,
output wire [WIDTH*HEIGHT-1:0] state,
output wire [31:0] generation
);
reg [WIDTH*HEIGHT-1:0] curr;
reg [31:0] gen_reg;
wire phase = gen_reg[0]; // 偶数步=0, 奇数步=1
wire [WIDTH*HEIGHT-1:0] nxt;
genvar bx, by;
generate
for (by = 0; by < HEIGHT/2; by = by + 1) begin : gen_brow
for (bx = 0; bx < WIDTH/2; bx = bx + 1) begin : gen_bcol
// 根据相位偏移块的起始位置
wire [6:0] ox = phase ? {1'b0, bx[5:1]} : {1'b0, bx};
wire [6:0] oy = phase ? {1'b0, by[5:1]} : {1'b0, by};
// 2×2块的4个元胞索引
wire [12:0] ul_idx = oy * WIDTH + ox;
wire [12:0] ur_idx = oy * WIDTH + ox + 1;
wire [12:0] ll_idx = (oy+1) * WIDTH + ox;
wire [12:0] lr_idx = (oy+1) * WIDTH + ox + 1;
// 4位块输入
wire [3:0] block_in = {curr[ul_idx], curr[ur_idx],
curr[ll_idx], curr[lr_idx]};
// 规则查找
wire [3:0] block_out = BLOCK_RULE[block_in * 4 +: 4];
// 写回
assign nxt[ul_idx] = block_out[3];
assign nxt[ur_idx] = block_out[2];
assign nxt[ll_idx] = block_out[1];
assign nxt[lr_idx] = block_out[0];
end
end
endgenerate
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
curr <= {WIDTH*HEIGHT{1'b0}};
gen_reg <= 32'd0;
end else if (init) begin
curr <= seed;
gen_reg <= 32'd0;
end else if (enable) begin
curr <= nxt;
gen_reg <= gen_reg + 32'd1;
end
end
assign state = curr;
assign generation = gen_reg;
endmodule可逆规则的条件：块变换必须是双射——每个4位输入映射到唯一的4位输出。
验证方法：检查规则的16个输出是否互不相同。
例如XOR奇偶规则 6996₁₆ = 0110100110010110₂：
输入0000→0, 0001→1, 0010→1, 0011→0, ...（每位是4输入的XOR）
这是自身的逆变换！应用两次回到原始状态。
| 特性 | Moore(8) | Von Neumann(4) | Hexagonal(6) | Margolus(4) |
|---|---|---|---|---|
| 邻居数 | 8 | 4 | 6 | 4(块) |
| 各向同性 | 近似 | 差 | 好 | 宏观好 |
| 规则空间 | 2^512 | 2^32 | 2^128 | 2^65536 |
| 硬件开销 | 高(8邻居) | 低(4邻居) | 中(6邻居) | 低(2×2块) |
| 可逆性 | 难以保证 | 难以保证 | 难以保证 | 天然可逆 |
| 适用场景 | 生命游戏 | 简单模型 | 物理仿真 | Lattice Gas |
你已经掌握了CA邻域设计的核心知识——从Moore到Von Neumann到Margolus，每种邻域都有其独特的优势和适用场景。
邻域的信息容量：
Moore邻域有9位输入（8邻居+自身），信息量 = log₂(2^9) = 9 bits
Von Neumann邻域有5位输入，信息量 = 5 bits
信息量的差异直接影响规则的"分辨率"——Moore邻域可以区分更多种情况
但更大的邻域也意味着更多的布线资源和更长的组合路径
面积-信息量权衡：
Moore: 8条邻居线 + 8输入MUX + 4位加法器 ≈ 30 LUTs/cell
Von Neumann: 4条邻居线 + 4输入MUX + 3位加法器 ≈ 12 LUTs/cell
信息效率：Moore = 9/30 = 0.30 bits/LUT, VN = 5/12 = 0.42 bits/LUT
Von Neumann邻域的信息效率更高！当面积受限时，VN是更好的选择
// 邻域比较器 - 计算Moore和VN邻域的差异
module neighborhood_compare #(
parameter WIDTH = 64
)(
input wire [WIDTH-1:0] row_above,
input wire [WIDTH-1:0] row_curr,
input wire [WIDTH-1:0] row_below,
output wire [3:0] moore_count [0:WIDTH-1],
output wire [2:0] vn_count [0:WIDTH-1],
output wire [WIDTH-1:0] diff // Moore≠VN的位置
);
genvar i;
generate
for (i = 0; i < WIDTH; i = i + 1) begin : gen_cmp
wire left = (i == 0) ? row_curr[WIDTH-1] : row_curr[i-1];
wire right = (i == WIDTH-1) ? row_curr[0] : row_curr[i+1];
// Von Neumann: 上下左右
assign vn_count[i] = row_above[i] + row_below[i] + left + right;
// Moore: 加上4个对角
wire ul = (i > 0) ? row_above[i-1] : row_above[WIDTH-1];
wire ur = (i < WIDTH-1) ? row_above[i+1] : row_above[0];
wire ll = (i > 0) ? row_below[i-1] : row_below[WIDTH-1];
wire lr = (i < WIDTH-1) ? row_below[i+1] : row_below[0];
assign moore_count[i] = vn_count[i] + ul + ur + ll + lr;
// 差异检测
assign diff[i] = (moore_count[i][2:0] != vn_count[i]);
end
endgenerate
endmodule关键发现：在大多数CA规则中，对角邻居对结果的影响远小于正交邻居。这意味着VN邻域虽然信息量少，但"性价比"更高。
实验数据（Conway Life Game）：
Moore邻域准确率：100%（定义）
VN邻域近似准确率：~85%（忽略对角信息）
面积比：VN只需Moore的40%资源
结论：对于面积受限的应用，VN邻域是很好的近似选择
元胞自动机课程 · 从Conway到Langton到Lattice Gas